#include <limits.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>

// Floyd(弗洛伊德)算法求解单源最短路径
// Ref: https://www.bilibili.com/video/BV19k4y1Q7Gj/?spm_id_from=333.999.0.0


typedef std::pair<int, int> pii;                // (节点, 权重)
typedef std::vector<std::vector<pii>> AdjList;  // AdjList邻接表;
typedef std::vector<std::vector<int>> Matrix;

AdjList edges = {{{1,4}, {7,8}},              // node0
                {{2,8}, {7,11}},              // node1
                {{1,8},{3,7},{8,2}},   
void floyd(Mat& adjmat, Mat& path) {
    int node_num = adjmat.size();
    for (int idx = 0; idx < node_num; idx++)  {     // 
        for (int i = 0; i < node_num; i++)  {
            for (int j = 0; j < node_num; j++)  {
                // if (i == j) continue;
                // if (idx == i || idx == j) continue;
                if ((adjmat[i][idx] + adjmat[idx][j]) < adjmat[i][j]) {
                    adjmat[i][j] = adjmat[i][idx] + adjmat[idx][j];
                    path[i][j]   = idx;
                }
            }
        }
    }
}


10}},  // node5
                {{7,1},{8,6},{5,2}},          // node6
                {{0,8},{1,11},{8,7},{6,1}},   // node7
                {{2,2},{7,7},{6,6}},   
void floyd(Mat& adjmat, Mat& path) {
    int node_num = adjmat.size();
    for (int idx = 0; idx < node_num; idx++)  {     // 
        for (int i = 0; i < node_num; i++)  {
            for (int j = 0; j < node_num; j++)  {
                // if (i == j) continue;
                // if (idx == i || idx == j) continue;
                if ((adjmat[i][idx] + adjmat[idx][j]) < adjmat[i][j]) {
                    adjmat[i][j] = adjmat[i][idx] + adjmat[idx][j];
                    path[i][j]   = idx;
                }
            }
        }
    }
}



void floyd(Mat& adjmat, Mat& path) {
    int node_num = adjmat.size();
    for (int idx = 0; idx < node_num; idx++)  {     // 
        for (int i = 0; i < node_num; i++)  {
            for (int j = 0; j < node_num; j++)  {
                // if (i == j) continue;
                // if (idx == i || idx == j) continue;
                if ((adjmat[i][idx] + adjmat[idx][j]) < adjmat[i][j]) {
                    adjmat[i][j] = adjmat[i][idx] + adjmat[idx][j];
                    path[i][j]   = idx;
                }
            }
        }
    }
}



 */
int floyd(AdjList& edges, Matrix& dist) {
    int numNodes = edges.size();

    // Initialize dist matrix with initial weights
    for (int i = 0; i < numNodes; ++i) {
        for (int j = 0; j < numNodes; ++j) {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = std::numeric_limits<int>::max();
        }
    }

    // Fill dist matrix with edge weights
    for (int i = 0; i < numNodes; ++i) {
        for (const auto& neighbor : edges[i]) {
            int j = neighbor.first;
            int weight = neighbor.second;
            dist[i][j] = weight;
        }
    }

    // Floyd-Warshall algorithm
    for (int k = 0; k < numNodes; ++k) {
        for (int i = 0; i < numNodes; ++i) {
            for (int j = 0; j < numNodes; ++j) {
                if (dist[i][k] != std::numeric_limits<int>::max() &&
                    dist[k][j] != std::numeric_limits<int>::max() &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Return 0 to indicate successful completion
    return 0;
}

/**
 * @brief  Floyd算法思路: 依次将每个节点作为中心点，区更新最短路径和最短距离
 * 
 * @matrix: 假设邻接矩阵的初始状态: -1表示初始状态
 *      邻接矩阵               D(-1): 任意两个节点的最短距离(初始为邻接矩阵)     Path(-1): 最短路径(前1节点)
 *      0   1   2                       0   1   2                            0   1   2             
 *  0   0   6   13                  0   6   13  0                         0  -1  0   0
 *  1   10  0   4                   1   10  0   4                         1  1   -1  1
 *  2   5  inf  0                   2   5   inf 0                         2  2   -1  -1
 * 
 * 
 *  step-1:  以0为中间节点区更新: 自己到自己的距离和路径都不用更新(即对角线的值不会变)
 *        ** 更新思路： 以指定节点为经过点，从src到dst的距离是否比之前的短， 如果短就更改距离和对应的path
 *        ** D(0)[2,1] 表示2经过0到1， 是否比当前2->1的距离短， 当前2->1 = inf, 2->0->1 = 5 + 6 = 11 < inf，即更新， 那Path[0][2,1] = 0
 *       D(0):                Path(0): 
 *     0   1   2              0   1   2             
 *  0  6   13  0           0  -1  0   0
 *  1  10  0   4           1  1   -1  1   D(0)[1,2] 不更新
 *  2  5   11  0           2  2   0  -1   D(0)[2,1] 更新
 * 
 *         经验可以发现： 假设要更新D(n), Path(n), 除了对角线元素不变外，第n行和n列的值也不用变!
 * 
 *  迭代次数： 此图有3个节点，需要更3次，即依次以0, 1, 2节点为经过点更新D和Path.
 * 
 * 
 *  最终结果:
 *      - 最短距离:  D(n)矩阵直接给出
 *      - 最短路径:  从src->dst的那一行，即Path(n)[src, dst], 反向倒推出dst->src经过的节点
 */


// g++ floyd.cpp -o main -std=c++11    
int main(int argc, char **argv) {
    const int INF = std::numeric_limits<int>::max();
    int numNodes  = edges.size();
    Matrix dist(numNodes, std::vector<int>(numNodes));

    floyd(edges, dist);

    // Output the shortest paths
    std::cout << "Shortest paths between nodes:" << std::endl;
    for (int i = 0; i < numNodes; ++i) {
        for (int j = 0; j < numNodes; ++j) {
            if (dist[i][j] == INF)
                std::cout << "INF ";
            else
                printf("%4d ", dist[i][j]);
        }
        printf("\n");
    }

    return 0;
}